Learning Parity with Noise (LPN)

LPNは、誤り訂正符号の理論に類似した、PQの有望な仮定である。

以下のように青い二つの行列が与えられた時に、赤い行列を特定したい。

これ自体は掃き出し法を用いることで特定することができる。

https://scrapbox.io/files/66c54c862d960f001ca533c6.png

しかし黄色いrandom行列を導入すると「青い行列だけ与えられた状態で赤い行列を特定する」問題は解くことが難しくなる

https://scrapbox.io/files/66c54caae6167e001c67761f.png

これは、ノイズを導入することで秘密の値を効果的に隠すものである。

LPNは誤り訂正符号の理論に似ており、LWEと類似していることから解くのが難しい問題であると推測され、ポスト量子耐性の仮定として利用されている。

LPN仮定は対称暗号において重要な仮定となっている。 LPN仮定は、暗号化方式、電子署名、認証プロトコルを含む様々な暗号プリミティブに利用されている。

これらの暗号システムの安全性は、ノイズの存在下で2進数の係数を持つ線形方程式を解くことの難しさに基づいており、これは困難な計算問題である。

The LPN problem is defined as follows:

$ A · s + e\mod p = u

Given a matrix A, it is computationally challenging to find a vector s that infinitely approximates a target vector u, even when a sparse noise vector e is randomly sampled within a fixed range. Here, the dot product is represented by “·”, p is a prime number greater than or equal to 2, s is an n-dimensional vector in the integer field of mod p, and the noise vector e is sparse with a small Hamming weight.

参考文献